现代优化是高层算法选择与底层机器感知之间的协作。尽管 渐近效率 定义了理论极限，但 性能至上 要求我们解决 常数因子 这些编译器无法单独处理的因子。
1. 优化层次结构
成功遵循线性过程：首先，消除 渐近低效 （例如，$O(N^2) \to O(N)$）。接着，解决 优化障碍——主要是 内存别名 以及函数调用开销（如恒定的 边界检查 在 get_vec_element中）。
2. 数据流与约束
编译器出于安全考虑而保守；如果指针 *dest 可能与向量 data重叠，它们就不会进行优化。我们通过 每元素周期数（CPE）来衡量实际运行速度。性能通常用缩放因子建模，例如 $\alpha = 0.974$，其中开销会使执行曲线偏移（例如，$209/\alpha = 39.0$）。
3. 硬件现实
优化需要理解 退休单元 和 关键路径。即使简单的循环也受限于功能单元的 吞吐量限制 或依赖链的 延迟限制 依赖链限制。
main.py
TERMINALbash — 80x24
> Ready. Click "Run" to execute.
>
QUESTION 1
Compare the performance of the three versions of bubblesort (4.47, 4.48, and 4.49). Why does one perform better?
4.49 is fastest because it reduces memory references and leverages conditional moves.
4.47 is fastest because array indexing is always faster than pointer arithmetic.
They all have the same CPE because the Big-O is $O(N^2)$.
4.48 is slowest due to stack spilling.
✅ Correct!
4.49 optimizes the inner loop logic to minimize branch misprediction penalties and redundant memory access.❌ Incorrect
Asymptotic complexity is identical, but constant factors like branch prediction and memory access patterns vary significantly.QUESTION 2
In the function
void swap(long *xp, long *yp) using the XOR/Addition trick, what happens if xp == yp?The values are successfully swapped.
The location is set to 0.
The program throws a segmentation fault.
The compiler optimizes it into a NOP.
✅ Correct!
This is a classic memory aliasing example. If the pointers are identical, the first operation *xp = *xp + *yp doubles the value, and the subsequent subtractions result in 0.❌ Incorrect
Think about the math: if $x$ and $y$ are the same location, $x = x + x \to 2x$; then $x = 2x - 2x \to 0$.QUESTION 3
Why does the version of polynomial evaluation in Practice Problem 5.5 run faster despite having more operations?
It uses more functional units.
It reduces the depth of the dependency chain (Critical Path).
It eliminates all floating-point multiplications.
It uses loop unrolling by a factor of 10.
✅ Correct!
Horner's method or reassociation reduces the sequence of dependent operations, allowing the CPU to start new calculations sooner (lower CPE).❌ Incorrect
Instruction count is not the only metric; the 'Critical Path' of dependencies often limits performance more than total work.QUESTION 4
What does the
Retirement Unit do in a modern out-of-order processor?It fetches instructions from memory.
It maintains sequential semantics and controls register file updates.
It performs floating-point multiplication.
It predicts branch directions.
✅ Correct!
It ensures that even though instructions execute out-of-order, they 'commit' their results to the architectural state in the correct program order.❌ Incorrect
The execution units do the work, but the Retirement Unit ensures the program remains logically sequential.QUESTION 5
Which of these is a significant 'Optimization Blocker' for GCC?
Asymptotic complexity.
Memory Aliasing.
Variable naming conventions.
The use of
long instead of int.✅ Correct!
Because the compiler cannot be sure two pointers don't point to the same address, it must perform safe, redundant memory reads/writes.❌ Incorrect
The compiler can handle types and names, but it cannot guess runtime memory addresses safely.Case Study: Pipeline Throughput Limits
Analyzing Performance Scaling in Pipelined Systems
Consider a system (Figure 4.32) divided into $k$ pipeline stages. Each stage has a functional delay of $300/k$ ps, and each pipeline register adds $20$ ps of overhead. We want to determine the limits of this architecture.
Q
1. What are the Latency and Throughput of the system as functions of $k$?
Solution:
The cycle time is the stage delay plus register delay: $C = (300/k + 20)$ ps. Latency $L = k \times C = k(300/k + 20) = 300 + 20k$ ps. Throughput $T = 1/C = 1 / (300/k + 20)$ instructions per picosecond. In GIPS (Giga-Instructions Per Second), this is $1000 / (300/k + 20)$.
The cycle time is the stage delay plus register delay: $C = (300/k + 20)$ ps. Latency $L = k \times C = k(300/k + 20) = 300 + 20k$ ps. Throughput $T = 1/C = 1 / (300/k + 20)$ instructions per picosecond. In GIPS (Giga-Instructions Per Second), this is $1000 / (300/k + 20)$.
Q
2. What is the ultimate limit on throughput as $k$ approaches infinity?
Solution:
As $k \to \infty$, the term $300/k$ approaches 0. The cycle time is then limited strictly by the register delay ($20$ ps). The maximum throughput is $1/20$ ps, which is $50$ GIPS.
As $k \to \infty$, the term $300/k$ approaches 0. The cycle time is then limited strictly by the register delay ($20$ ps). The maximum throughput is $1/20$ ps, which is $50$ GIPS.